//Given an integer array of size n, find all elements that appear more than ⌊ n/
//3 ⌋ times. 
//
// Follow-up: Could you solve the problem in linear time and in O(1) space? 
//
// 
// Example 1: 
//
// 
//Input: nums = [3,2,3]
//Output: [3]
// 
//
// Example 2: 
//
// 
//Input: nums = [1]
//Output: [1]
// 
//
// Example 3: 
//
// 
//Input: nums = [1,2]
//Output: [1,2]
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5 * 104 
// -109 <= nums[i] <= 109 
// 
// Related Topics 数组 哈希表 计数 排序 
// 👍 405 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

//Java：Majority Element II
class P229MajorityElementIi {
    public static void main(String[] args) {
        Solution solution = new P229MajorityElementIi().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> majorityElement(int[] nums) {
            int len = nums.length;
            int avg = len / 3 + 1;
            Map<Integer, Integer> map = new HashMap<>(len);
            for (int num : nums) {
                map.compute(num, (k, v) -> v == null ? 1 : v + 1);
            }
            return map.entrySet().stream().filter(e -> e.getValue() >= avg).map(e -> e.getKey()).collect(Collectors.toList());

        }

        public List<Integer> majorityElementMore(int[] nums) {
            // 创建返回值
            List<Integer> res = new ArrayList<>();
            if (nums == null || nums.length == 0) return res;
            // 初始化两个候选人candidate，和他们的计票
            int cand1 = nums[0], count1 = 0;
            int cand2 = nums[0], count2 = 0;

            // 摩尔投票法，分为两个阶段：配对阶段和计数阶段
            // 配对阶段
            for (int num : nums) {
                // 投票
                if (cand1 == num) {
                    count1++;
                    continue;
                }
                if (cand2 == num) {
                    count2++;
                    continue;
                }

                // 第1个候选人配对
                if (count1 == 0) {
                    cand1 = num;
                    count1++;
                    continue;
                }
                // 第2个候选人配对
                if (count2 == 0) {
                    cand2 = num;
                    count2++;
                    continue;
                }

                count1--;
                count2--;
            }

            // 计数阶段
            // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
            count1 = 0;
            count2 = 0;
            for (int num : nums) {
                if (cand1 == num) count1++;
                else if (cand2 == num) count2++;
            }

            if (count1 > nums.length / 3) res.add(cand1);
            if (count2 > nums.length / 3) res.add(cand2);

            return res;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}